/*
 *https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/
 *902. 最大为 N 的数字组合
 *difficult 吴朝泽 2024.9.20
 *数位DP
 这道题目不同的所在之处是，填数字不能从 0-9 之间随便选了，而是要符合题目 digits 数组给的数字，
 而题目给的是字符串类型，先将字符串中的数字(字符串型)转为整数，同时记录某个数字是否出现过，
 出现就在 dic 数组中将他赋为 1 ，出现了才可以使用
*/


class Solution {
public:
    int arr[30];
    long long dp[30];
    int dic[10];    //dic 数组用来记录哪些元素可用，如果 dic[i] == 1 表示可以用，等于 0 表示不可用 

    //pos 表示当前位数，flag 表示填的数字大小是否受到限制，lead 表示是否含有前导零
    long long DFS(int pos, bool flag, bool lead)
    {
        if(pos == 0)  return 1;
        if(!flag && dp[pos] != -1 && !lead)  return dp[pos];

        int max_num = flag ? arr[pos] : 9;
        long long res = 0;
        for(int i = 0; i <= max_num; ++i)
        {
            //优先判断 dic[i] 是否为 0
            if(dic[i] == 0) continue;   

            /*讨论前导零的使用情况
              !lead: 如果 lead 为 false，表示当前数字已经填入有效数字，前导零不再被考虑。
              (lead && pos == 0): 如果 lead 为 true，这意味着还在处理前导零，但只有在 pos 为 0 的时候（即正在填入最高位的数字）才允许使用零。
              整个条件的目的是确保在填入数字时，如果填的是零，只有在没有前导数字的情况下才能填入（即最高位是零），从而避免形成无效的数字。
            */
            if(i == 0 && (!lead || (lead && pos == 0)))  continue;

            res += DFS(pos-1, flag && (i == max_num), lead && (i == 0));
        }
        /*分类讨论
          如果 flag 为 true，表示数字的填入受到上界限制，那么无论前面是否有前导零，都应该返回当前的结果 res。
          如果 lead 为 true，表示当前仍在填入前导零，这种情况下也应该返回 res。
          如果 flag || lead 为 true，则直接返回 res，表示可以返回当前计算的结果。
          如果 flag 和 lead 都为 false，则意味着当前填入的数字已经超出了上界的限制，也不是前导零的情况。
          此时，将当前的结果 res 存储到动态规划数组 dp[pos] 中，以便后续可以重用，并返回 res。
        */
        return flag || lead ? res : dp[pos] = res;
    }

    long long check(long long x)
    {
        int pos = 0;
        while(x)
        {
            arr[++pos] = x % 10;
            x /= 10;
        }
        return DFS(pos, 1, 1) - 1;
    }

    int atMostNGivenDigitSet(vector<string>& digits, int n)
    {
        memset(arr, 0, sizeof(arr));
        memset(dp, -1, sizeof(dp));
        memset(dic, 0, sizeof(dic));

        //将字符串参数中的每个数字都转换为整数
        //atoi(v.c_str()): 调用将字符串转换为对应的整数(例如，如果 v 是 "3"，则 atoi 返回 3)
        //如果 dic[i] = 1 则表示 i 是可用的，0 则不可用
        for(auto &v:digits)  dic[atoi(v.c_str())]=1;

        dic[0] = 1;
        return check(n);
    }
};